package com.example.temp;

public class Test16 {

    public static void main(String[] args) {

    }

    /**
     * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
     */

    public class TreeNode {

        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }


    public class Solution {
        public boolean HasSubtree(TreeNode root1, TreeNode root2) {
            if (root1 == null || root2 == null) return false;


            //需要满足其中一个条件1、当前树结构相同2、左子树结构相同3、右子树结构相同
            return helper(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
        }

        //该函数判断结构是否相同
        private boolean helper(TreeNode root1, TreeNode root2) {

            if (root2 == null) return true;
            if (root1 == null) return false;
            //需要同时满足1、根节点相同2、左子树结构相同3、右子树结构相同
            return root1.val == root2.val&& helper(root1.left, root2.left) && helper(root1.right, root2.right);
        }

//        public boolean HasSubtreeTest(TreeNode root1, TreeNode root2){
//
//        }
    }
}
